Ik ben momenteel bezig met het schrijven van een basisparser voor een XML-smaak. Als oefening implementeer ik een LL-tabelgestuurde parser. Dit is mijn voorbeeld van BNF-grammatica: % token name gegevensreeks %% / * LL (1) * / doc: elem elem: "<" open_tag open_tag: naam attr close_tag close_tag: ">" elem_or_data "" elem_or_data: "<" open_tag elem_or_data data elem_or_data / * epsilon * / attr: name ":" string attr / * epsilon * / Is deze grammatica correct? Elke letterlijke terminal staat tussen aanhalingstekens. De abstracte terminals worden gespecificeerd door% token. Ik codeer een handgeschreven lexer om mijn invoer om te zetten in een tokenslijst. Hoe zou ik de abstracte terminals tokeniseren?
2021-03-03 08:10:44
De klassieke benadering zou zijn om een reguliere expressie (of een andere herkenner) te schrijven voor elke mogelijke terminal.
Wat u "abstracte" terminals noemt, die perfect concreet zijn, zijn in feite terminals waarvan de bijbehorende patronen meer dan één mogelijke invoerstring herkennen. De werkelijk herkende tekenreeks (of een berekende functie van die tekenreeks) moet aan de parser worden doorgegeven als de semantische waarde van het token.
Nominaal zal de tokeniser op elk punt in de invoertekenreeks alle herkenners uitvoeren en degene met de langste overeenkomst kiezen. (Dit is de zogenaamde "maximale munch" -regel.) Dit kan meestal worden geoptimaliseerd, vooral als alle patronen reguliere expressies zijn. (F) lex zal die optimalisatie bijvoorbeeld voor u doen.
Een complicatie in uw geval is dat de tokenisering van uw taal contextafhankelijk is. In het bijzonder, wanneer het doel elem_or_data is, zijn de enige mogelijke tokens <,